#include <bits/stdc++.h>

using namespace std;

#define ll long long
class Solution{
public:
    int maxGoodNumber(vector<int> &nums){
        auto solve=[&](vector<int>&vec)->ll{
            ll ret=0;
            for(int x: vec){
                vector<int> tmp;
                for(int y=x;y;y>>=1) tmp.push_back(y&1);
                while(!tmp.empty()) ret=ret*2+tmp.back(), tmp.pop_back();
            }
            return ret;
        };
        ll ans=0;
        for(int i=0;i<6;i++){
            ans=max(ans,solve(nums));
            next_permutation(nums.begin(),nums.end());
        } return ans;
    }
};

class Solution2{
public:
    vector<int> remainingMethods(int n,int K,vector<vector<int>>& invocations){
        vector<int> e[n]; for(auto &edge: invocations) e[edge[0]].push_back(edge[1]);
        bool bad[n]; memset(bad,0,sizeof(bad)); queue<int>q; q.push(K); bad[K]=true;
        while(!q.empty()){
            int sn=q.front(); q.pop();
            for(int fn:e[sn])
                if(!bad[fn]) {
                    q.push(fn); bad[fn]=true;}
        }
        for(int sn=0;sn<n;sn++)
            if(!bad[sn]){
                for(int fn:e[sn])
                    if(bad[fn]){
                        vector<int>ans;
                        for(int i=0;i<n;i++) ans.push_back(i);
                        return ans;
                    }
            }
        vector<int>ans;
        for(int i=0;i<n;i++) if(!bad[i])ans.push_back(i);
        return ans;
    }
};

class Solution3 {
public:
    vector<vector<int>> constructGridLayout(int n, vector<vector<int>>& edges) {
        vector<int> as(n);
        vector<vector<int>> e(n);
        for(auto& q:edges){
            ++as[q[0]];
            ++as[q[1]];
            e[q[0]].push_back(q[1]);
            e[q[1]].push_back(q[0]);
        }
        int k=min_element(as.begin(),as.end())-as.begin();
        vector<vector<int>> res;
        queue<tuple<int,int,int>> q;
        q.push({0,0,k});
        res.push_back({k});
        vector<bool> col(n);
        col[k]=1;
        while(!q.empty()){
            int s=q.size();
            for(int i=0;i<s;++i){
                auto f=q.front();
                q.pop();
                int x=get<0>(f);
                int y=get<1>(f);
                int ind=get<2>(f);
                int a=-1,b=-1;
                for(int z:e[ind]){
                    if(!col[z]){
                        if(a==-1){
                            a=z;
                        }
                        else{
                            b=z;
                        }
                    }
                }
                if(b!=-1){
                    if(as[b]>as[a]){
                        swap(a,b);
                    }
                    res.push_back({b});
                    col[b]=1;
                    q.push({x+1,y,b});
                }
                if(a!=-1){
                    res[x].push_back(a);
                    col[a]=1;
                    q.push({x,y+1,a});
                }


            }
        }
        return res;
    }
};

class Solution4{
public:
    vector<int> gcdValues(vector<int> &nums, vector<ll>&queries){
        int m=*max_element(nums.begin(),nums.end());
        vector<long long> a(m+1),b(m+1);
        for(int q:nums){
            ++a[q];
        }
        for(int i=1;i<=m;++i){
            for(int j=i;j<=m;j+=i){
                b[i]+=a[j];
            }
            b[i]=b[i]*(b[i]-1)/2;
        }
        for(int i=m;i>=1;--i){
            for(int j=i*2;j<=m;j+=i){
                b[i]-=b[j];
            }
        }
        vector<long long> c;
        long long s=0;
        for(long long q:b){
            c.push_back(s+=q);
        }
        vector<int> res;
        for(auto q:queries){
            res.push_back(upper_bound(c.begin(),c.end(),q)-c.begin());
        }
        return res;
    }
};
int main(){
    vector<int> a={1,2,3};
    Solution s1; cout<<s1.maxGoodNumber(a)<<endl;
    vector<vector<int>> nums={{1,2},{0,1},{3,2}};
    Solution2 s2; vector<int> a2=s2.remainingMethods(4,1,nums); for(auto a:a2) cout<<a<<" "; cout<<endl;
    vector<vector<int>> a3={{0,1},{0,2},{1,3},{2,3}};
    Solution3 s3; vector<vector<int>> ans3=s3.constructGridLayout(4,a3); for(auto a:ans3){ for(auto a1:a) {cout<<a1<<" ";}; cout<<" | ";}; cout<<endl;
    vector<int> n={2,3,4}; vector<ll> q={0,2,2};
    Solution4 s4; vector<int> a4=s4.gcdValues(n,q); for(auto a: a4) cout<<a<<" "; cout<<endl;
}